#include<iostream>

class MyLinkedList {
public:
// 单链表
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode():val(0), next(nullptr){}
        ListNode(int x):val(x), next(nullptr){}
        ListNode(int x, ListNode *next):val(x), next(next){}
    };

    MyLinkedList() {
        head = nullptr;
    }
    
    int get(int index) {
        if (index < 0)
        {
            return -1;
        }
        else if(index == 0)
        {
            if (head == nullptr)
            {
                return -1;
            }
            else
            {
                return head->val;
            }
        }
        else if(head == nullptr)
        {
            return -1;
        }     

        int pre_index = 0;
        ListNode *current_node = head;//dummyNode;
        while (current_node->next != nullptr)
        {
            if (pre_index == index-1)
            {
                return current_node->next->val;
            }
            pre_index++;
            current_node = current_node->next;
        }   

        return -1;
    }
    
    void addAtHead(int val) {
        if (head == nullptr)
        {
            head = new ListNode(val);
        }
        else
        {
            ListNode* tmp = head;
            head = new ListNode(val);
            head->next = tmp;
        }
    }
    
    void addAtTail(int val) {
        ListNode *dummyNode = new ListNode();
        dummyNode->next = head;
        ListNode *current_node = dummyNode;
        while (current_node->next != nullptr)
        {
            current_node = current_node->next;
        }
        ListNode *new_node = new ListNode(val);
        current_node->next = new_node;
        head = dummyNode->next;
        delete dummyNode;
    }
    
    void addAtIndex(int index, int val) {
        if (index < 0)
        {
            return;
        }
        else if  (0 == index)
        {
            addAtHead(val);
            return;
        }
        else if (head == nullptr)
        {
            return;
        }
        
        int pre_index = 0;
        ListNode *current_node = head;//dummyNode;
        while (current_node->next != nullptr)
        {
            if (pre_index == index-1)
            {
                ListNode *new_node = new ListNode(val);
                new_node->next = current_node->next;
                current_node->next = new_node;
                return;
            }
            pre_index++;
            current_node = current_node->next;
        }
        
        // 如果 `index `等于链表的长度，那么该节点会被追加到链表的末尾
        if (current_node->next == nullptr && pre_index == index-1)
        {
            addAtTail(val);
        }
    }
    
    void deleteAtIndex(int index) {
        if (index < 0)
        {
            return;
        }
        else if(index == 0)
        {
            if (head == nullptr)
            {
                return;
            }
            else
            {
                ListNode *tmp = head;
                head = head->next;
                delete tmp;
                return;
            }
        }
        else if(head == nullptr)
        {
            return;
        }
        
        int pre_index = 0;
        ListNode *current_node = head;//dummyNode;
        while (current_node->next != nullptr)
        {
            if (pre_index == index-1)
            {
                ListNode *deleted_node = current_node->next;
                current_node->next = current_node->next->next;
                delete deleted_node;
                return;
            }
            pre_index++;
            current_node = current_node->next;
        }
    }
private:
    ListNode *head;
};

int main()
{
    MyLinkedList *myLinkedList = new MyLinkedList();
    /*
    // case1: 
    myLinkedList->addAtHead(7);
    std::cout << "1: "<< myLinkedList->get(0) <<std::endl;
    myLinkedList->addAtHead(2);
    std::cout << "2: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1) <<std::endl;
    myLinkedList->addAtHead(1);
    std::cout << "3: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2) <<std::endl;
    myLinkedList->addAtIndex(3, 0);    
    std::cout << "4: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3) <<std::endl;
    myLinkedList->deleteAtIndex(2);
    std::cout << "5: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2) <<std::endl;
    myLinkedList->addAtHead(6);
    std::cout << "6: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3) <<std::endl;
    myLinkedList->addAtTail(4);
    std::cout << "7: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3)<<", "<< myLinkedList->get(4) <<std::endl;
    myLinkedList->addAtHead(4);
    std::cout << "8: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3)<<", "<< myLinkedList->get(4)<<", "<< myLinkedList->get(5) <<std::endl;
    myLinkedList->addAtIndex(5, 0);
    std::cout << "9: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3)
    <<", "<< myLinkedList->get(4)<<", "<< myLinkedList->get(5) <<", "<< myLinkedList->get(6)<<std::endl;
    myLinkedList->addAtHead(6);
    std::cout << "10: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3)
    <<", "<< myLinkedList->get(4)<<", "<< myLinkedList->get(5) <<", "<< myLinkedList->get(6) <<", "<< myLinkedList->get(7)<<std::endl;
    */

    // case2:   
    myLinkedList->addAtHead(1);
    std::cout << "1: "<< myLinkedList->get(0) <<std::endl;
    myLinkedList->addAtTail(3);
    std::cout << "2: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1) <<std::endl;
    myLinkedList->addAtIndex(1,2);
    std::cout << "3: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2) <<std::endl;
    myLinkedList->deleteAtIndex(0);
    std::cout << "4: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1) <<std::endl;

    return 0;
}